Search results for "Top-down parsing"

showing 2 items of 2 documents

The complexity of graph languages generated by hyperedge replacement

1990

Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.

ParsingTheoretical computer scienceComputer Networks and CommunicationsComputer sciencebusiness.industryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Parsing expression grammarcomputer.software_genreTop-down parsingTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESParser combinatorS-attributed grammarTop-down parsing languageArtificial intelligenceL-attributed grammarbusinesscomputerComputer Science::Formal Languages and Automata TheorySoftwareNatural language processingInformation SystemsBottom-up parsingActa Informatica
researchProduct

On parsing optimality for dictionary-based text compression—the Zip case

2013

Dictionary-based compression schemes are the most commonly used data compression schemes since they appeared in the foundational paper of Ziv and Lempel in 1977, and generally referred to as LZ77. Their work is the base of Zip, gZip, 7-Zip and many other compression software utilities. Some of these compression schemes use variants of the greedy approach to parse the text into dictionary phrases; others have left the greedy approach to improve the compression ratio. Recently, two bit-optimal parsing algorithms have been presented filling the gap between theory and best practice. We present a survey on the parsing problem for dictionary-based text compression, identifying noticeable results …

Theoretical computer scienceComputer scienceData_CODINGANDINFORMATIONTHEORYTop-down parsingcomputer.software_genreTheoretical Computer ScienceParsing optimalityCompression (functional analysis)Discrete Mathematics and CombinatoricsLossless compressionParsingLZ77 algorithmSettore INF/01 - InformaticaDeflate algorithmbusiness.industryDictionary-based text compressionComputational Theory and MathematicsData compressionDEFLATECompression ratioArtificial intelligencebusinesscomputerNatural language processingBottom-up parsingData compressionJournal of Discrete Algorithms
researchProduct